package LeetCode.String;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * # 6. 字符串同构
 * <p>
 * 205\. Isomorphic Strings (Easy)
 * [力扣](https://leetcode-cn.com/problems/isomorphic-strings/description/)
 * 205. 同构字符串
 * 给定两个字符串 s 和 t，判断它们是否是同构的。
 * 如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。
 * 所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。
 * <p>
 * 示例 1:
 * 输入: s = "egg", t = "add"
 * 输出: true
 * <p>
 * 示例 2:
 * 输入: s = "foo", t = "bar"
 * 输出: false
 * <p>
 * 示例 3:
 * 输入: s = "paper", t = "title"
 * 输出: true
 * <p>
 * 说明:
 * 你可以假设 s 和 t 具有相同的长度。
 */

public class Test6 {

    public static String modelStr(String s) {
        char[] arr = s.toCharArray();
        int i = 1;
        String modelStr = "";
        HashMap hashMap = new HashMap();
        for (char c : arr) {
            if (hashMap.containsKey(c)) {
                modelStr += "" + hashMap.get(c);
            } else {
                hashMap.put(c, i);
                modelStr += "" + i++;
            }
        }
        return modelStr;
    }

    //6. 字符串同构
    public static boolean isIsomorphic(String s, String t) {
        return modelStr(s).equals(modelStr(t));
    }


    //github cycc解法
    //记录一个字符上次出现的位 置，如果两个字符串中的字符上次出现的位置一样，那么就属于同构。
    public boolean isIsomorphic3(String s, String t) {
        int[] preIndexOfS = new int[256];
        int[] preIndexOfT = new int[256];
        for (int i = 0; i < s.length(); i++) {
            char sc = s.charAt(i), tc = t.charAt(i);
            if (preIndexOfS[sc] != preIndexOfT[tc]) {
                return false;
            }
            preIndexOfS[sc] = i + 1;
            preIndexOfT[tc] = i + 1;
        }
        return true;
    }

    //评论区解法
    /**
     * https://leetcode-cn.com/problems/isomorphic-strings/solution/javake-neng-bi-jiao-jian-dan-de-xie-fa-by-hao-fei-/
     * 字符串中，同一个位置的字符在本串中第一次出现的位置相同。
     * 我简单解释一下，本题判定为false有这些个情况，我们假设拿s串和t串作对比
     * 1.s串中相同的字符，对应的t串中的字符并不相等
     * 2.s串中不同的字符，对应的t串中的字符却是相等的
     * 所以判断的关键点就是相同的字符要对应相同的字符，
     * 那么相同字符处于后位置的字符的第一次出现的位置就应该相同。
     * 所以我们在判断时，只需要判断两个字符串同位置的字符是否相同即可。
     */
    class Solution {
        public boolean isIsomorphic(String s, String t) {
            char[] ch1 = s.toCharArray();
            char[] ch2 = t.toCharArray();
            int len = s.length();
            for (int i = 0; i < len; i++) {
                if(s.indexOf(ch1[i]) != t.indexOf(ch2[i])){
                    return false;
                }
            }
            return true;
        }

        // //同上思路，Map实现 时间复杂度O(n) 空间复杂度O(n)
        public boolean isIsomorphic2(String s, String t) {
            if (s == null || t == null || s.length() != t.length()) return false;
            char[] sc = s.toCharArray();
            char[] tc = t.toCharArray();
            Map<Character, Integer> map1 = new HashMap<>();
            Map<Character, Integer> map2 = new HashMap<>();
            for (int i = 0; i < sc.length; i++) {

                if (!map1.containsKey(sc[i])) {
                    map1.put(sc[i], i);
                }
                if (!map2.containsKey(tc[i])) {
                    map2.put(tc[i], i);
                }
                if(map1.get(sc[i]).intValue() != map2.get(tc[i]).intValue()) return false;
            }
            return true;
        }
    }

    public static void main(String[] args) {
        System.out.println("6. 字符串同构");
        String str="people";
        System.out.println("modelStr方法测试"+str+" "+modelStr(str));

        String s = "egg", t = "add";
        System.out.println(isIsomorphic(s,t));

        String s2 = "foo", t2 = "bar";
        System.out.println(isIsomorphic(s2,t2));

        String s3 = "paper", t3 = "title";
        System.out.println(isIsomorphic(s3,t3));
    }
}
